package DoExercise.HSP_ZCY.A010_排序算法系列;


import DoExercise.JianzhiOffer.Offer000_Common;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 快速排序：时间复杂度：o(n log n) 空间复杂度：o(log n) 不稳定算法
 *
 * 99万个数字 耗时 1s
 */
public class A006_快速排序1
{
    
    public static void main(String[] args)
    {
        int[] array = {9, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        quickSort(array);
        for (int i : array)
        {
            System.out.print(i + " ");
        }
    
//        SimpleDateFormat startTime = new SimpleDateFormat("yyyy:MM:dd:HH:mm:ss");
//        System.out.println("排序开始时间：" + startTime.format(new Date()));
//        quickSort_1_test();
//        SimpleDateFormat endTime = new SimpleDateFormat("yyyy:MM:dd:HH:mm:ss");
//        System.out.println("排序结束时间：" + endTime.format(new Date()));
        
    }
    
    /**
     * 加这一层是为了程序控制
     *
     * @param array
     */
    public static void quickSort(int[] array)
    {
        int len;
        if (array == null
                || (len = array.length) == 0
                || len == 1)
        {
            return;
        }
        recQuickSort(array, 0, len - 1);
    }
    
    public static void recQuickSort(int[] arr, int left, int right)
    {
        if (left > right) return;
        int base = arr[left];
        int i = left, j = right;
        while (i < j)
        {
            //从右边开始是因为pivot在左边
            while (arr[j] >= base && i < j) j--;
            while (arr[i] <= base && i < j) i++;
            //交换位置
            if (i < j) Offer000_Common.swap(arr, i, j);
        }
        //遍历完成，交换哨兵
        Offer000_Common.swap(arr, left, j);
        recQuickSort(arr, left, j - 1);
        recQuickSort(arr, j + 1, right);
    }
    
    
    public static void quickSort_1_test()
    {
        //测试80万个数据的排序
        int[] arrTest = new int[99999999];
        for (int index = 0; index < 99999999; index++)
        {
            arrTest[index] = (int) (Math.random() * 99999999);
        }
        //增量gap，并逐步缩小增量
        quickSort(arrTest);
    }
    
    
    /**
     *
     * 第二种快速排序的方法，不太理解
     *
     * @param a
     * @param start
     * @param end
     */
    private static void quickSort_2(int[] a, int start, int end)
    {
        if (start < end)
        {
            int p = quickSort_2_core(a, start, end);
            quickSort_2(a, start, p - 1);
            quickSort_2(a, p + 1, end);
        }
    }
    
    private static int quickSort_2_core(int[] a, int start, int end)
    {
        int x = a[end];//以x作为锚点
        int i = start;
        for (int j = start; j <= end - 1; j++)
        {
            if (a[j] >= x)
            {
                Offer000_Common.swap(a, i, j);
                i++;//交换了几次
            }
        }//把最大的放到最后
        Offer000_Common.swap(a, i, end);//把最大的放到i的位置
        return i;
    }
    
    /**
     * 不基于比较器的算法
     * 前缀树：可以统计以某个字符串开始的字符出现过多少次
     */
    public static class Code01_TrieTree
    {
        public static class Node1
        {
            public int pass;
            public int end;
            public Node1[] nexts;
            
            public Node1()
            {
                pass = 0;
                end = 0;
                nexts = new Node1[26];
            }
        }
        
        public static class Trie1
        {
            private Node1 root;
            
            public Trie1()
            {
                root = new Node1();
            }
            
            public void insert(String word)
            {
                if (word == null) return;
                char[] chs = word.toCharArray();
                Node1 node = root;
                node.pass++;
                int index = 0;
                for (int i = 0; i < chs.length; i++)
                {
                    index = chs[i] - 'a';
                    if (node.nexts[index] == null)
                    {
                        node.nexts[index] = new Node1();
                    }
                    node = node.nexts[index];
                    node.pass++;
                }
                node.end++;
            }
            
            public void delete(String word)
            {
                if (search(word) != 0)
                {
                    char[] chs = word.toCharArray();
                    Node1 node = root;
                    node.pass--;
                    int index = 0;
                    for (int i = 0; i < chs.length; i++)
                    {
                        index = chs[i] - 'a';
                        if (--node.nexts[index].pass == 0)
                        {
                            node.nexts[index] = null;
                            return;
                        }
                        node = node.nexts[index];
                    }
                    node.end--;
                }
            }
            
            public int search(String word)
            {
                if (word == null) return 0;
                char[] chs = word.toCharArray();
                Node1 node = root;
                int index = 0;
                for (int i = 0; i < chs.length; i++)
                {
                    index = chs[i] - 'a';
                    if (node.nexts[index] == null) return 0;
                    node = node.nexts[index];
                }
                return node.end;
            }
            
            // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
            public int prefixNumber(String pre)
            {
                if (pre == null) return 0;
                char[] chs = pre.toCharArray();
                Node1 node = root;
                int index = 0;
                for (int i = 0; i < chs.length; i++)
                {
                    index = chs[i] - 'a';
                    if (node.nexts[index] == null) return 0;
                    node = node.nexts[index];
                }
                return node.pass;
            }
        }
        
        public static class Node2
        {
            public int pass;
            public int end;
            public HashMap<Integer, Node2> nexts;
            
            public Node2()
            {
                pass = 0;
                end = 0;
                nexts = new HashMap<>();
            }
        }
        
        public static class Trie2
        {
            private Node2 root;
            
            public Trie2()
            {
                root = new Node2();
            }
            
            public void insert(String word)
            {
                if (word == null)
                {
                    return;
                }
                char[] chs = word.toCharArray();
                Node2 node = root;
                node.pass++;
                int index = 0;
                for (int i = 0; i < chs.length; i++)
                {
                    index = (int) chs[i];
                    if (!node.nexts.containsKey(index))
                    {
                        node.nexts.put(index, new Node2());
                    }
                    node = node.nexts.get(index);
                    node.pass++;
                }
                node.end++;
            }
            
            public void delete(String word)
            {
                if (search(word) != 0)
                {
                    char[] chs = word.toCharArray();
                    Node2 node = root;
                    node.pass--;
                    int index = 0;
                    for (int i = 0; i < chs.length; i++)
                    {
                        index = (int) chs[i];
                        if (--node.nexts.get(index).pass == 0)
                        {
                            node.nexts.remove(index);
                            return;
                        }
                        node = node.nexts.get(index);
                    }
                    node.end--;
                }
            }
            
            // word这个单词之前加入过几次
            public int search(String word)
            {
                if (word == null)
                {
                    return 0;
                }
                char[] chs = word.toCharArray();
                Node2 node = root;
                int index = 0;
                for (int i = 0; i < chs.length; i++)
                {
                    index = (int) chs[i];
                    if (!node.nexts.containsKey(index))
                    {
                        return 0;
                    }
                    node = node.nexts.get(index);
                }
                return node.end;
            }
            
            // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
            public int prefixNumber(String pre)
            {
                if (pre == null)
                {
                    return 0;
                }
                char[] chs = pre.toCharArray();
                Node2 node = root;
                int index = 0;
                for (int i = 0; i < chs.length; i++)
                {
                    index = (int) chs[i];
                    if (!node.nexts.containsKey(index))
                    {
                        return 0;
                    }
                    node = node.nexts.get(index);
                }
                return node.pass;
            }
        }
        
        public static class Right
        {
            
            private HashMap<String, Integer> box;
            
            public Right()
            {
                box = new HashMap<>();
            }
            
            public void insert(String word)
            {
                if (!box.containsKey(word))
                {
                    box.put(word, 1);
                } else
                {
                    box.put(word, box.get(word) + 1);
                }
            }
            
            public void delete(String word)
            {
                if (box.containsKey(word))
                {
                    if (box.get(word) == 1)
                    {
                        box.remove(word);
                    } else
                    {
                        box.put(word, box.get(word) - 1);
                    }
                }
            }
            
            public int search(String word)
            {
                if (!box.containsKey(word))
                {
                    return 0;
                } else
                {
                    return box.get(word);
                }
            }
            
            public int prefixNumber(String pre)
            {
                int count = 0;
                for (String cur : box.keySet())
                {
                    if (cur.startsWith(pre))
                    {
                        count += box.get(cur);
                    }
                }
                return count;
            }
        }
        
        // for test
        public static String generateRandomString(int strLen)
        {
            char[] ans = new char[(int) (Math.random() * strLen) + 1];
            for (int i = 0; i < ans.length; i++)
            {
                int value = (int) (Math.random() * 6);
                ans[i] = (char) (97 + value);
            }
            return String.valueOf(ans);
        }
        
        // for test
        public static String[] generateRandomStringArray(int arrLen, int strLen)
        {
            String[] ans = new String[(int) (Math.random() * arrLen) + 1];
            for (int i = 0; i < ans.length; i++)
            {
                ans[i] = generateRandomString(strLen);
            }
            return ans;
        }
        
        public static void main(String[] args)
        {
            int arrLen = 100;
            int strLen = 20;
            int testTimes = 100000;
            for (int i = 0; i < testTimes; i++)
            {
                String[] arr = generateRandomStringArray(arrLen, strLen);
                Trie1 trie1 = new Trie1();
                Trie2 trie2 = new Trie2();
                Right right = new Right();
                for (int j = 0; j < arr.length; j++)
                {
                    double decide = Math.random();
                    if (decide < 0.25)
                    {
                        trie1.insert(arr[j]);
                        trie2.insert(arr[j]);
                        right.insert(arr[j]);
                    } else if (decide < 0.5)
                    {
                        trie1.delete(arr[j]);
                        trie2.delete(arr[j]);
                        right.delete(arr[j]);
                    } else if (decide < 0.75)
                    {
                        int ans1 = trie1.search(arr[j]);
                        int ans2 = trie2.search(arr[j]);
                        int ans3 = right.search(arr[j]);
                        if (ans1 != ans2 || ans2 != ans3)
                        {
                            System.out.println("Oops!");
                        }
                    } else
                    {
                        int ans1 = trie1.prefixNumber(arr[j]);
                        int ans2 = trie2.prefixNumber(arr[j]);
                        int ans3 = right.prefixNumber(arr[j]);
                        if (ans1 != ans2 || ans2 != ans3)
                        {
                            System.out.println("Oops!");
                        }
                    }
                }
            }
            System.out.println("finish!");
            
        }
        
    }
    
    /**
     * 计数排序也是一种桶排序
     * 所有的桶排序都需要对输入的数据类型进行限制
     * <p>
     * 比如计数排序需要限制输入数组的长度在2000内
     */
    public static class Code02_CountSort
    {
        public static void countSort(int[] arr)
        {
            //找出数组中最大的数字，并new出这么大的数组
            if (arr == null || arr.length < 2) return;
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < arr.length; i++) max = Math.max(max, arr[i]);
            int[] bucket = new int[max + 1];
            //计数排序
            for (int i = 0; i < arr.length; i++)
            {
                bucket[arr[i]]++;
            }
            int i = 0;
            for (int j = 0; j < bucket.length; j++)
            {
                while (bucket[j]-- > 0)
                {
                    arr[i++] = j;
                }
            }
        }
        
        public static void comparator(int[] arr)
        {
            Arrays.sort(arr);
        }
        
        public static int[] generateRandomArray(int maxSize, int maxValue)
        {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++)
            {
                arr[i] = (int) ((maxValue + 1) * Math.random());
            }
            return arr;
        }
        
        // for test
        public static int[] copyArray(int[] arr)
        {
            if (arr == null)
            {
                return null;
            }
            int[] res = new int[arr.length];
            for (int i = 0; i < arr.length; i++)
            {
                res[i] = arr[i];
            }
            return res;
        }
        
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2)
        {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null))
            {
                return false;
            }
            if (arr1 == null && arr2 == null)
            {
                return true;
            }
            if (arr1.length != arr2.length)
            {
                return false;
            }
            for (int i = 0; i < arr1.length; i++)
            {
                if (arr1[i] != arr2[i])
                {
                    return false;
                }
            }
            return true;
        }
        
        // for test
        public static void printArray(int[] arr)
        {
            if (arr == null)
            {
                return;
            }
            for (int i = 0; i < arr.length; i++)
            {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
        
        // for test
        public static void main(String[] args)
        {
            int testTime = 500000;
            int maxSize = 100;
            int maxValue = 150;
            boolean succeed = true;
            for (int i = 0; i < testTime; i++)
            {
                int[] arr1 = generateRandomArray(maxSize, maxValue);
                int[] arr2 = copyArray(arr1);
                countSort(arr1);
                comparator(arr2);
                if (!isEqual(arr1, arr2))
                {
                    succeed = false;
                    printArray(arr1);
                    printArray(arr2);
                    break;
                }
            }
            System.out.println(succeed ? "Nice!" : "Fucking fucked!");
            int[] arr = generateRandomArray(maxSize, maxValue);
            printArray(arr);
            countSort(arr);
            printArray(arr);
        }
        
    }
    
    /**
     * 基数排序
     * 前提：正数且是十进制
     */
    public static class Code03_RadixSort
    {
        public static void radixSort(int[] arr)
        {
            if (arr == null || arr.length < 2)
            {
                return;
            }
            radixSort(arr, 0, arr.length - 1, maxbits(arr));
        }
        
        //最大值有几位
        public static int maxbits(int[] arr)
        {
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < arr.length; i++)
            {
                max = Math.max(max, arr[i]);
            }
            int res = 0;
            while (max != 0)
            {
                res++;
                max /= 10;
            }
            return res;
        }
        
        public static void radixSort(int[] arr, int L, int R, int digit)
        {
            final int radix = 10;
            int i = 0, j = 0;
            int[] help = new int[R - L + 1];
            for (int d = 1; d <= digit; d++)
            {
                int[] count = new int[radix];
                //入桶操作
                for (i = L; i <= R; i++)
                {
                    j = getDigit(arr[i], d);
                    count[j]++;
                }
                //出桶操作
                for (i = 1; i < radix; i++)
                {
                    count[i] = count[i] + count[i - 1];
                }
                for (i = R; i >= L; i--)
                {
                    j = getDigit(arr[i], d);
                    help[count[j] - 1] = arr[i];
                    count[j]--;
                }
                //根据出桶顺序重新排序
                for (i = L, j = 0; i <= R; i++, j++)
                {
                    arr[i] = help[j];
                }
            }
        }
        
        //确定一个数字从后向前对应的位数,d表示位数
        public static int getDigit(int x, int d)
        {
            return ((x / ((int) Math.pow(10, d - 1))) % 10);
        }
        
        
        // for test
        public static void comparator(int[] arr)
        {
            Arrays.sort(arr);
        }
        
        // for test
        public static int[] generateRandomArray(int maxSize, int maxValue)
        {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++)
            {
                arr[i] = (int) ((maxValue + 1) * Math.random());
            }
            return arr;
        }
        
        // for test
        public static int[] copyArray(int[] arr)
        {
            if (arr == null)
            {
                return null;
            }
            int[] res = new int[arr.length];
            for (int i = 0; i < arr.length; i++)
            {
                res[i] = arr[i];
            }
            return res;
        }
        
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2)
        {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null))
            {
                return false;
            }
            if (arr1 == null && arr2 == null)
            {
                return true;
            }
            if (arr1.length != arr2.length)
            {
                return false;
            }
            for (int i = 0; i < arr1.length; i++)
            {
                if (arr1[i] != arr2[i])
                {
                    return false;
                }
            }
            return true;
        }
        
        // for test
        public static void printArray(int[] arr)
        {
            if (arr == null)
            {
                return;
            }
            for (int i = 0; i < arr.length; i++)
            {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
        
        // for test
        public static void main(String[] args)
        {
    //        int testTime = 500000;
    //        int maxSize = 100;
    //        int maxValue = 100000;
    //        boolean succeed = true;
    //        for (int i = 0; i < testTime; i++)
    //        {
    //            int[] arr1 = generateRandomArray(maxSize, maxValue);
    //            int[] arr2 = copyArray(arr1);
    //            radixSort(arr1);
    //            comparator(arr2);
    //            if (!isEqual(arr1, arr2))
    //            {
    //                succeed = false;
    //                printArray(arr1);
    //                printArray(arr2);
    //                break;
    //            }
    //        }
    //        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    //
    //        int[] arr = generateRandomArray(maxSize, maxValue);
    //        printArray(arr);
    //        radixSort(arr);
    //        printArray(arr);
        
        }
        
    }
}
